#include <cstdlib>
#include <iostream>
#include <queue>
#include <omp.h>

/*
 * Dijkstra: explained in the sequential code
 */
#define N 1003
#define INF 0x3f3f3f3f

using namespace std;

typedef pair < int, int > ii;

vector <int> graph[N], weight[N];
int dis[N][N];

void dijkstra(int source, int * distance, int n)
{
	priority_queue < ii , vector < ii >, greater < ii > > q;
	for(int i = 1; i <= n; i++)
		distance[i] = INF;

	distance[source] = 0;
	q.push( make_pair ( distance[source], source ) );
	
	while(!q.empty()) {
		int cur = q.top().second;
		int disCur = q.top().first;
		q.pop();

		if( disCur > distance[cur] ) continue;

		for(int i = 0; i < graph[cur].size(); i++) {
			int u = graph[cur][i];
			int w = weight[cur][i];
		
			if( distance[u] > disCur + w) {
				distance[u] = disCur + w;
				q.push( make_pair( distance[u], u ));
			}
		}
	}
}

int main (int argc, char ** argv)
{
	int n, m;
	int a, b, c;

	// this program receives the number of threads as input
	if( argc != 2) {
		cout << "usage: ./par <num_threads>\n"; 
		exit(1);
	}

	// get the number of threads
	int n_threads = atoi(argv[1]);

	// run the input
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		graph[a].push_back(b);
		graph[b].push_back(a);
		weight[a].push_back(c);
		weight[b].push_back(c);
	}

	// answer for each node (the other most far node)
	int ans[N];

	// set the number of threads to be used
	omp_set_num_threads(n_threads);
	

	// split the work among the available threads
	#pragma omp parallel for 
	for(int i = 1; i <= n; i++) {
		dijkstra(i, dis[i], n);

		ans[i] = 0;
		for(int j = 1; j <= n; j++) 
			if( dis[i][j] != INF )
				ans[i] = max(ans[i], dis[i][j]);
	}

	int result = INF;

	// get the answer
	for(int i = 1; i <= n; i++) 
		result = min(result, ans[i]);

	cout << result << "\n";

	return 0;
}
